package Leetcode.ArrayAndLinkedList.climbStairs70;

/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * <p>
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * <p>
 * 注意：给定 n 是一个正整数。
 * 输入： 3
 * 输出： 3
 * 解释： 有三种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶 + 1 阶
 * 2.  1 阶 + 2 阶
 * 3.  2 阶 + 1 阶
 * <p>
 * 1 : 1
 * 2 : 2
 * 3 : f(1) + f(2)
 * 4 : f(2) + f(3)
 * n : f(n-1) + f(n-2)
 * 我们发现如果要到n级台阶 要么从n-1迈一步 或n-2迈两步
 */

/**
 * 次数： 2
 */
public class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int f1 = 1;
        int f2 = 2;
        int f3 = 3;
        for (int index = 3; index <= n; index++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.climbStairs(3));
    }
}


/**
 * public int climbStairs(int n) {
 * if (n <= 2) {
 * return n;
 * }
 * int f1 = 1;
 * int f2 = 2;
 * int f3 = 3;
 * for(int i = 3; i <= n; ++i) {
 * f3 = f1 + f2;
 * f1 = f2;
 * f2 = f3;
 * }
 * return f3;
 */
